package com.tgy.leetcode;

import java.util.HashMap;

/**
 * @Author: tgy
 * @Date: 12/26/20 3:03 PM
 */
public class _138_复制带随机指针的链表_01 {

    public Node copyRandomList(Node head) {

        if (head == null) {

            return null;
        }

        Node node = head;
        // 添加新节点
        while (node != null) {

            Node newNode = new Node(node.val);
            Node tmpNext = node.next;
            node.next = newNode;
            newNode.next = tmpNext;
            node = tmpNext;
        }

        node = head;
        // 设置 random
        while (node != null) {

            node.next.random =  node.random == null ? null:node.random.next;
            node = node.next.next;
        }

        Node newHead = head.next;
        Node newTail = head.next;
        Node olfTail = head;


        node = head.next.next;

        // 设置 next
        while (node != null) {


            olfTail.next = node;
            olfTail = node;
            newTail.next = node.next;
            newTail = node.next;

            node = node.next.next;
        }

        //  注意最后要设置next=null
        olfTail.next = null;
        return newHead;
    }
}
